package 简单;

/*
*  按奇偶排序数组 II 
* 力扣地址：https://leetcode-cn.com/problems/sort-array-by-parity-ii/
* 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
* 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
* 你可以返回任何满足上述条件的数组作为答案。
* 示例：
* 输入：[4,2,5,7]
* 输出：[4,5,2,7]
* 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
* 思路:先遍历将奇数放到一个数组，在遍历将偶数放到一个数组。
* */

import java.util.Arrays;

public class demo922 {

    public static void main(String[] args) {

        int[] a = {4,2,5,7};

        System.out.println(Arrays.toString(sortArrayByParityII(a)));

    }

    //改进
    public static int[] sortArrayByParityII(int[] A)
    {
        int[] ts = new int[A.length];
        int rc=0,jc=1;

        for (int t:A){

            if (t%2 == 0)
            {
                ts[rc] = t;
                rc += 2;
            }
            else
            {
                ts[jc] = t;
                jc += 2;
            }
        }

        return ts;
    }

    //第一次成功 最优
    public static int[] sortArrayByParityII2(int[] A)
    {
        int[] r = new int[A.length/2];
        int[] j = new int[A.length/2];
        int rc=0,jc=0;

        for (int t:A){

            if (t%2 == 0)
            {
                r[rc++] = t;
            }
            else
            {
                j[jc++] = t;
            }
        }

//        Arrays.sort(r);
//        Arrays.sort(j);

        rc=0;
        jc=0;
        for (int i=0;i<A.length;i++){

            if (i%2==0)
            {
                A[i] = r[rc++];
            }
            else
            {
                A[i] = j[jc++];
            }

        }

        return A;

    }


    //超时
//    public static int[] sortArrayByParityII(int[] A) {
//
//        for (int i=0;i<A.length;i++){
//
//            if (i%2 == 0)
//            {
//                if (A[i]%2 != 0)
//                {
//                    for (int j=i;j<A.length;j++){
//
//                        if (A[j]%2==0){
//                            int t = A[i];
//                            A[i] = A[j];
//                            A[j] = t;
//                        }
//
//                    }
//                }
//            }
//            else
//            {
//                if (A[i]%2 == 0)
//                {
//                    for (int j=i;j<A.length;j++){
//
//                        if (A[j]%2 !=0){
//                            int t = A[i];
//                            A[i] = A[j];
//                            A[j] = t;
//                        }
//
//                    }
//                }
//            }
//
//        }
//
//        return A;
//
//    }
}
